/* 
 * [New BSD License (BSD 3-Clause License)]
 * Copyright (c) 2012, Max Bechtold
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 *     - Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     - Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     - Neither the name of the Rel2Xml Project nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package maxbe.rel2xml.generator;

import static maxbe.rel2xml.util.Config.getBoolean;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

import javax.xml.transform.TransformerConfigurationException;
import javax.xml.transform.sax.TransformerHandler;

import maxbe.rel2xml.generator.docs.DataType;
import maxbe.rel2xml.generator.docs.HandlerController;
import maxbe.rel2xml.generator.docs.constraints.References;
import maxbe.rel2xml.grammar.FillTableException;
import maxbe.rel2xml.grammar.MapTableException;
import maxbe.rel2xml.util.Config;

import org.apache.log4j.Logger;
import org.xml.sax.SAXException;
import org.xml.sax.helpers.AttributesImpl;

/**
 * Represents a relational table with additional information for mapping to
 * XML.</br> A table A is <i>dependent</i> of a table B if there is a
 * relationship defined in such a way that for every tuple of B (which defines
 * its own <i>context</i>) n tuples of A will be generated. (cmp.
 * "fill table A with n per B").</br> The number of references to
 * <i>dependent</i> foreign keys per context equals the number of generated A
 * tuples per B tuple and thus allows counting. Independent foreign keys do not
 * guarantee this equality. A table A can be modelled as a <i>child</i> of a
 * table B if it depends <i>primarily</i> on B (i.e. B comes first in A's
 * dependency list (cmp. "per B and C"). This enables tuples of A to be stored
 * in a subtree of the element that represents the referred B tuple (cmp.
 * "map table A under B"). Thereby, dependent foreign key columns of A referring
 * to B can be omitted during generation as they are implicitly expressed by A's
 * tuples being stored in the referenced B tuples.</br> For performance reasons,
 * tuples of a context are generated in blocks of a fixed size of BLOCK_SIZE.
 * 
 * @author Max Bechtold
 * 
 */
public class Table {

	/**
	 * Defines whether a table is to be mapped as a subtree in the single
	 * document of all tables, or to a document of its own, or as a collection
	 * consisting of documents for each tuple in the table.
	 */
	public static enum Mapping {
		SUBTREE,

		DOCUMENT,

		COLLECTION,
	}

	private static Logger log = Logger.getLogger(Table.class);

	/** The name of this table */
	private final String name;

	/** A list containing all the columns of this table in a defined order */
	private final ArrayList<Column> columns;

	/** The number of tuples that are prepared and generated in a row */
	private static final int BLOCK_SIZE = 10000;

	/** Table under which this table is to be mapped */
	private Table parent;

	/** Tables that will be mapped under this table */
	private List<Table> children;

	/** Tables that are dependent of this table */
	private List<Table> dependents;

	/** Tables that this table is dependent on */
	private List<Table> dependencies;

	/**
	 * Filling factor, either an absolute number/range or a multiplicity
	 * regarding the dependencies
	 */
	private FillFactor fillFactor;

	/** Number of tuples in table; computed regarding dependencies */
	private int cardinality = -1;

	/** Number of context tuples */
	private int base = -1;

	/** Counter for current context tuple */
	private int currContext;

	/** Defines mapping strategy */
	private Mapping mapping = Mapping.SUBTREE;

	/**
	 * TransformerHandler that cares about formatting the document and writing
	 * it to disk
	 */
	private TransformerHandler handler;

	public Table(String name) {
		this.name = name;
		columns = new ArrayList<Column>();
		dependencies = new ArrayList<Table>();
		dependents = new ArrayList<Table>();
		children = new ArrayList<Table>();
	}

	public String getName() {
		return name;
	}

	public String getXPathSelector() {
		return getXPathSelector(false, true);
	}

	public String getXPathSelector(boolean relative) {
		return getXPathSelector(relative, true);
	}

	public String getXPathSelector(boolean relative, boolean toInstance) {
		return ((parent != null && !relative) ? parent.getXPathSelector() : "")
				+ "/" + name + "s/" + (toInstance ? name : "");
	}

	public List<Column> getColumns() {
		return columns;
	}

	public Column getColumn(String name) {
		for (Column column : columns) {
			if (column.getName().equals(name)) {
				return column;
			}
		}
		return null;
	}

	public List<Column> getRefColumns() {
		return getRefColumns(null);
	}

	/**
	 * Returns all columns that reference a key of the given table. If
	 * <i>table</i> is null, columns referencing any column will be returned
	 */
	public List<Column> getRefColumns(Table table) {
		ArrayList<Column> result = new ArrayList<Column>();
		for (Column column : columns) {
			Column refColumn = column.getRefColumn();
			if (refColumn != null && !column.isDerived()
					&& (table == null || refColumn.getTable().equals(table))) {
				result.add(column);
			}
		}
		return result;
	}

	public List<Table> getDependencies() {
		return dependencies;
	}

	public List<Table> getDependents() {
		return dependents;
	}

	public Table getParent() {
		return parent;
	}

	public FillFactor getFillFactor() {
		return fillFactor;
	}

	public int getFactor() {
		// Make sure base is calculated as fillFactor needs this information
		fillFactor.setNumber(getBase());
		return fillFactor.getFactor();
	}

	public int[] getFactors() {
		// Make sure base is calculated as fillFactor needs this information
		fillFactor.setNumber(getBase());
		return fillFactor.getFactors();
	}

	public int getBase() {
		if (base == -1) {
			base = 1;
			for (Table table : dependencies) {
				base *= table.getCardinality();
			}
		}
		return base;
	}

	public int getCardinality() {
		if (cardinality == -1) {
			// First calculate base as fillFactor needs that information
			fillFactor.setNumber(getBase());
			cardinality = fillFactor.getSum();
		}
		return cardinality;
	}

	public Mapping getMapping() {
		return mapping;
	}

	public List<Table> getChildren() {
		return children;
	}

	public boolean isAncestorOf(Table table) {
		if (this == table)
			return true;
		else if (children.contains(table))
			return true;
		else
			for (Table child : children)
				if (child.isAncestorOf(table))
					return true;
		return false;
	}

	public boolean isPrimaryAncestorOf(Table table) {
		if (this == table)
			return true;
		else if (children.indexOf(table) == 0)
			return true;
		else if (children.size() > 0
				&& children.get(0).isPrimaryAncestorOf(table))
			return true;
		else
			return false;
	}

	public void addColumn(Column column) {
		column.setTable(this);
		columns.add(column);
	}

	public void setParent(Table table) {
		if (parent != null) {
			String msg = String.format(
					"Table '%s' already mapped under table '%s'.", name,
					parent.getName());
			log.error(msg);
			throw (new MapTableException(msg));
		}

		if (!dependsOn(table, false, true)) {
			String msg = String
					.format("Cannot map table '%s' under table '%s' without a chain of primary dependencies between them.",
							name, table.getName());
			log.error(msg);
			throw (new MapTableException(msg));
		}

		// This way, hand-made relationships, i.e. via DerivedValues or
		// underived ValueConstructors are possible, though now the user must
		// check the semantics
		if (!getBoolean(Config.MAP_UNCHECKED)
				&& !referencesDependentlyInContext(table, true,
						new ArrayList<Table>())) {
			String msg = String
					.format("Table '%s' cannot be mapped under '%s' without having at least one dependent, not random "
							+ "foreign key referencing '%s' or a foreign key referencing a table in the chain of primary dependencies "
							+ "to '%s' whose refContext is contained in that dependency chain as well.",
							name, table.getName(), table.getName(),
							table.getName());
			log.error(msg);
			throw (new MapTableException(msg));
		}

		this.parent = table;
		table.addChild(this);
	}

	private boolean referencesDependentlyInContext(Table parent,
			boolean markImplicit, List<Table> refChain) {
		List<Column> columns = getRefColumns();
		Iterator<Column> it = columns.iterator();
		boolean dependent = false;

		// Continue searching if references are to hide if possible or if
		// dependent not yet set
		while (it.hasNext() && (markImplicit || !dependent)) {
			Column column = it.next();
			if (column.getDataConstraint().getValueConstructor() instanceof References) {
				References reference = (References) column.getDataConstraint()
						.getValueConstructor();
				Table refTable = column.getRefColumn().getTable();
				Table refContext = reference.getRefContext();

				// Make sure not to end up in a loop
				if (refChain.contains(refTable))
					continue;

				if (reference.isDependent() && !reference.isRandom()) {
					if (refTable == parent) {
						// First case: Direct dependent, not random reference to
						// parent
						dependent = true;
						if (markImplicit)
							// In exactly this situation foreign keys are
							// implicit through the mapping
							column.setImplicit(true);
					} else if (refTable.dependsOn(parent, false, false)) {
						// Second case: Direct dependent, not random reference
						// to a table that referencesDependentlyInContext parent
						refChain.add(refTable);
						dependent = refTable.referencesDependentlyInContext(
								parent, false, refChain);
					}
				} else if (refTable.dependsOn(parent, false, false)
						&& refContext != null
						&& (refContext == parent || refContext.dependsOn(
								parent, false, false))) {
					// Third case: Possibly random reference to a table
					// depending from parent
					// with a refContext equal to or depending from parent where
					// that table
					// referencesDependentlyInContext parent
					refChain.add(refTable);
					dependent = refTable.referencesDependentlyInContext(parent,
							false, refChain);
				}
			}
		}
		return dependent;
	}

	public void setMapping(Mapping mapping) {
		this.mapping = mapping;
	}

	public void addDependency(Table dependency) {
		if (dependency == this) {
			String msg = String.format(
					"Cannot make table '%s' dependent on itself.", name);
			log.error(msg);
			throw (new FillTableException(msg));
		}

		if (dependency.dependsOn(this, true, false)) {
			String msg = String
					.format("Making table '%s' dependent on '%s' would result in a cyclic dependency.",
							name, dependency.getName());
			log.error(msg);
			throw (new FillTableException(msg));
		}

		dependencies.add(dependency);
	}

	/**
	 * Find out if table target is in the dependency hierarchy of a table.</br>
	 * Cascading allows for searching in secondary, tertiary and so forth
	 * dependencies like per A and B and C... which is not desired in some cases
	 * (e.g. uniqueness and reference contexts).</br> If factor checking is
	 * requested, an exception is thrown if varying factors are encountered on
	 * the way to the target table.
	 */
	public boolean dependsOn(Table target, boolean cascade, boolean checkFactors) {
		return getDependencyChain(target, cascade, checkFactors) != null;
	}

	private List<Table> getDependencyChain(Table target, boolean cascade,
			boolean checkFactors) {
		List<Table> chain = null;
		boolean contained = false;
		Iterator<Table> deps = (cascade || dependencies.size() == 0 ? dependencies
				: dependencies.subList(0, 1)).iterator();

		while (deps.hasNext() && !contained) {
			Table dep = deps.next();
			contained = dep.equals(target);

			if (contained) {
				chain = new ArrayList<Table>();
				chain.add(this);
				chain.add(dep);
			} else {
				chain = dep.getDependencyChain(target, cascade, checkFactors);
				if (chain != null) {
					if (checkFactors && dep.getFillFactor().varies()) {
						// Easy solution: No varying filling factors allowed
						String msg = String
								.format("Cannot have table '%s' as context as there are varying fill factors specified in the dependency chain.",
										target.getName());
						log.error(msg);
						throw (new FillTableException(msg));
					}
					chain.add(0, this);
				}
			}
		}
		return chain;
	}

	/**
	 * Determines the number of iterations through table target. If target is a
	 * primary dependency, this number equals target.cardinality. Otherwise,
	 * target.cardinality is multiplied on each dependency level by the
	 * predecessing tables' cardinality
	 * 
	 */
	public int howManyIterationsThrough(Table target) {
		boolean contained = false;
		int factor = 1;
		Iterator<Table> deps = dependencies.iterator();

		while (deps.hasNext() && !contained) {
			Table dep = deps.next();
			contained = dep.equals(target);
			if (contained) {
				factor *= dep.getCardinality();
			} else {
				int recResult = dep.howManyIterationsThrough(target);
				contained = (recResult != -1);
				if (contained) {
					factor *= recResult;
				} else {
					factor *= dep.getCardinality();
				}
			}
		}

		return contained ? factor : -1;
	}

	public void addDependent(Table dependent) {
		dependents.add(dependent);
	}

	public void setFillFactor(FillFactor fillFactor) {
		this.fillFactor = fillFactor;
	}

	public void addChild(Table child) {
		children.add(child);
	}

	@Override
	public String toString() {
		String result = String.format("Table '%s'", name);
		if (parent != null) {
			result += " under " + parent.getName();
		}
		result += " (";
		for (Column col : columns) {
			result += col.toString() + ", ";
		}

		result = result.substring(0, result.length() - 2) + ")";
		// if (dependencies.size() > 0)
		// {
		// result += " depends on ";
		// for (Table table : dependencies)
		// {
		// result += table.getName() + ", ";
		// }
		// result = result.substring(0, result.length() - 2);
		// }

		return result;
	}

	private void setHandler(TransformerHandler handler) {
		this.handler = handler;
		for (Table child : children) {
			child.setHandler(handler);
		}
	}

	/**
	 * Generates the tuples of a table. In case of children tables, their
	 * respective methods will be called for every new tuple.</br>
	 * 
	 * @param handler
	 *            TransformerHandler to use for serialization
	 * @throws SAXException
	 *             if handler throws one for some reason
	 * @throws IOException
	 * @throws TransformerConfigurationException
	 */
	public void populate(HandlerController hc) throws SAXException,
			TransformerConfigurationException, IOException {
		initPopulate();

		if (mapping == Mapping.SUBTREE) {
			setHandler(hc.getHandler());
			handler.startElement(null, null, name + 's', null);
		} else if (mapping == Mapping.DOCUMENT) {
			setHandler(hc.getHandler(name));
			handler.startElement(null, null, name + 's', null);
		}

		// For each context, generate dependent tuples.
		// Possibly only a single iteration, if table is independent or
		// table this one depends on has cardinality 1

		generateContexts(hc, getBase());

		if (mapping == Mapping.SUBTREE) {
			handler.endElement(null, null, name + 's');
		} else if (mapping == Mapping.DOCUMENT) {
			handler.endElement(null, null, name + 's');
			hc.terminateHandler(handler);
		}
	}

	private void generateContexts(HandlerController hc, int number)
			throws SAXException, TransformerConfigurationException, IOException {
		int end = currContext + number;
		while (currContext < end) {
			generateContext(hc, getFactor());
			currContext++;
		}

	}

	private void generateContext(HandlerController hc, int contextSize)
			throws SAXException, TransformerConfigurationException, IOException {
		for (Column column : columns) {
			column.mark(currContext);
		}

		int count = 0;
		while (count + BLOCK_SIZE <= contextSize) {
			generateBlock(hc, BLOCK_SIZE);
			count += BLOCK_SIZE;
		}

		int rest = contextSize - count;
		if (rest > 0) {
			generateBlock(hc, rest);
		}
	}

	private void generateBlock(HandlerController hc, int blockSize)
			throws SAXException, TransformerConfigurationException, IOException {
		List<List<String>> values = new ArrayList<List<String>>();
		List<Iterator<String>> its = new ArrayList<Iterator<String>>();

		for (Column column : columns) {
			List<String> list = column.next(blockSize);
			values.add(list);
			its.add(list.iterator());
		}

		for (int i = 0; i < blockSize; i++) {
			if (mapping == Mapping.COLLECTION) {
				setHandler(hc.getHandler(name, i));
				handler.startDocument();
			}

			Iterator<Iterator<String>> it = its.iterator();

			// Handle attributes first
			AttributesImpl atts = new AttributesImpl();
			for (Column column : columns) {
				Iterator<String> valIt = it.next();
				if (column.getMapping() == Column.Mapping.XML_ATTRIBUTE
						&& (!getBoolean(Config.IMPLICIT_FKEYS) || !column
								.isImplicit())) {
					String next = valIt.next();

					if (next == null && !getBoolean(Config.OMIT_NULLS))
						next = "";

					if (next != null) {
						atts.addAttribute(null, null, column.getName(), null,
								next);
					}
				}
			}

			handler.startElement(null, null, name, atts);

			// Then append elements
			it = its.iterator();
			for (Column column : columns) {
				Iterator<String> valIt = it.next();
				if (column.getMapping() == Column.Mapping.XML_ELEMENT
						&& (!getBoolean(Config.IMPLICIT_FKEYS) || !column
								.isImplicit())) {
					String next = valIt.next();

					if (next == null && !getBoolean(Config.OMIT_NULLS))
						next = "";

					if (next != null) {
						char[] value = next.toCharArray();
						handler.startElement(null, null, column.getName(), null);
						handler.characters(value, 0, value.length);
						handler.endElement(null, null, column.getName());
					}
				}
			}

			// Last, append child elements
			for (Table child : children) {
				handler.startElement(null, null, child.getName() + 's', null);

				/*
				 * In total (as this line will be executed cardinality times)
				 * child.base contexts will be created, just as if child would
				 * not be mapped under this table
				 */
				child.generateContexts(hc, child.getBase() / getCardinality());

				handler.endElement(null, null, child.getName() + 's');
			}

			handler.endElement(null, null, name);

			if (mapping == Mapping.COLLECTION) {
				handler.endDocument();
				hc.terminateHandler(handler);
			}
		}
	}

	public void initPopulate() {
		boolean announce = false;
		for (Column column : columns) {
			if (column.needsAnnounce()) {
				announce = true;
				break;
			}
		}

		// Announce cardinality if necessary
		if (announce) {
			for (Column column : columns) {
				column.announce(getCardinality());
			}
		}

		currContext = 0;

		for (Table child : children) {
			child.initPopulate();
		}
	}

	public int estimateCardinality() {
		if (dependencies.size() == 0) {
			return getCardinality();
		} else {
			int card = 1;
			for (Table dep : dependencies)
				card *= dep.estimateCardinality();
			return (int) Math.round(card * fillFactor.getAverage());
		}
	}

	public static class FillFactor {

		private Logger log = Logger.getLogger(FillFactor.class);

		/** Total number of factors to be generated */
		private int number;

		/** Column with integer values that will be used as factors */
		private final Column sourceColumn;

		/** If true, generated values vary in a certain range */
		private final boolean varies;

		/**
		 * Pregenerated numbers of values that will be generated in each new
		 * context
		 */
		private int[] factors;

		private final int min;
		private final int max;
		private final int per;
		private int sum = -1;
		private int factorIndex = 0;

		private final Random rand1;
		private final Random rand2;

		private static long seed1 = 324677211;
		private static long seed2 = 472854187;

		public FillFactor(int min, int max, int per) {
			this.min = min;
			this.max = max;
			this.per = per;
			this.sourceColumn = null;
			this.varies = (max > -1 || per > 1);
			rand1 = new Random(seed1++);
			rand2 = new Random(seed2++);
		}

		public FillFactor(int number) {
			this(number, -1, 1);
		}

		public FillFactor(int min, int max) {
			this(min, max, 1);
		}

		public FillFactor(Column sourceColumn) {
			if (sourceColumn.getDataType() != DataType.INTEGER) {
				String msg = String
						.format("Cannot derive fill factors from column '%s' as it is not of type INTEGER.",
								sourceColumn.getName());
				log.error(msg);
				throw (new FillTableException(msg));
			}

			this.min = -1;
			this.max = -1;
			this.per = 1;
			this.varies = true;
			rand1 = null;
			rand2 = null;
			this.sourceColumn = sourceColumn;
		}

		public boolean varies() {
			return varies;
		}

		public Column getSourceColumn() {
			return sourceColumn;
		}

		public void setNumber(int number) {
			this.number = number;
		}

		private int getFactor() {
			if (varies() || per != 1) {
				if (factors == null)
					prepareFactors();
				return factors[factorIndex++];
			} else {
				return min;
			}
		}

		private int[] getFactors() {
			if (factors == null)
				prepareFactors();
			return factors;
		}

		private int getSum() {
			if (sum == -1)
				if (max > -1 || sourceColumn != null)
					prepareFactors();
				else
					sum = number * min;

			return sum;
		}

		private void prepareFactors() {
			factors = new int[number];
			sum = 0;
			if (sourceColumn != null) {
				List<String> prepVals = sourceColumn.prepareValues();
				for (int i = 0; i < factors.length; i++) {
					int factor = Integer.parseInt(prepVals.get(i));
					factors[i] = factor;
					sum += factor;
				}
			} else if (per != 1) {
				int offset = 0;

				for (int i = 0; i < factors.length; i++) {
					if (offset > 0) {
						offset--;
						factors[i] = 0;
					} else {
						// Compute normally distributed values in a 25% margin
						// around per
						offset = per - per / 4 + rand2.nextInt(2 * per / 4 + 1)
								- 1;
						int factor = 0;
						if (max > -1)
							factor = rand1.nextInt(max - min + 1) + min;
						else
							factor = min;
						factors[i] = factor;
						sum += factor;
					}
				}
			} else {
				for (int i = 0; i < factors.length; i++) {
					int factor = rand1.nextInt(max - min + 1) + min;
					factors[i] = factor;
					sum += factor;
				}
			}
		}

		public double getAverage() {
			if (varies) {
				return (min + max) / 2.0;
			} else if (sourceColumn != null) {
				// Guess a meaningful number
				return 10;
			} else {
				return min;
			}
		}

		@Override
		public String toString() {
			if (per == 1) {
				if (max > -1) {
					return String.format("[%d, %d]", min, max);
				} else {
					return String.valueOf(min);
				}
			} else {
				return String.valueOf(min + " per " + per);
			}
		}

	}
}